import java.util.*;
import java.io.*;

public class test {
    public static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static Read in = new Read();
    // 蓝桥杯 跳石头(2024-国赛)
    public static int n;
    public static int max;
    public static int[] arr;
    public static boolean[] count;
    public static void main1(String[] args) throws IOException{
        n = in.nextInt();
        arr = new int[n + 1];
        for(int i = 1;i <= n;i++){
            arr[i] = in.nextInt();
        }
        count = new boolean[n + 1];
        for(int i = 1;i <= n;i++){
            HashSet<Integer> set = new HashSet<>();
            dfs(i,set);
            max = Math.max(max,set.size());
            count = new boolean[n + 1];
        }
        System.out.println(max);
    }
    public static void dfs(int start, HashSet<Integer> set) {
        if (start > n || count[start]) return;
        count[start] = true; // 标记当前石头已访问
        set.add(arr[start]);   // 添加权值到集合
        // 尝试两种跳跃方式
        int n1 = start + arr[start];
        int n2 = start * 2;
        dfs(n1, set);
        dfs(n2, set);
    }
    // 蓝桥杯 园丁(2024-国赛)
    // 树中节点的数量
    static public int n1 ,ans = 0;
    // 节点值
    static public int[] a = new int[100086];
    // 节点值的平方自由部分
    static public int[] f = new int[100086];
    // 邻接表表示树
    static public List<Integer>[] tree;
    public static void main(String[] args) throws IOException{
        n1 = in.nextInt();
        for (int i = 1; i <= n1; i++) {
            a[i] = in.nextInt();
            f[i] = squareFree(a[i]); // 计算每个节点值的平方自由部分
        }
        tree = new ArrayList[n1 + 1];
        for (int i = 1; i <= n1; i++) tree[i] = new ArrayList<>();
        for (int i = 1; i < n1; i++) {
            int u = in.nextInt(); int v = in.nextInt();
            tree[u].add(v);tree[v].add(u);
        }
        dfs(1, 0);
        System.out.println(ans);
    }
    static public int squareFree(int x) {
        int res = 1;
        for (int i = 2; i * i <= x; i++) {
            int cnt = 0;
            while (x % i == 0) {
                x /= i;
                cnt++;
            }
            if ((cnt & 1) == 1) res *= i;  // 如果质因数的幂次为奇数，将其乘到结果中
        }
        if (x > 1) res *= x;   // 如果 x 还有剩余的质因数，也乘到结果中
        return res;
    }
    static public void dfs(int u, int fa) {
        List<Integer> children = new ArrayList<>();
        // 遍历当前节点 u 的所有邻接节点 v
        for(int v: tree[u]) {
            // 不是父节点，加入children
            if(v != fa){
                children.add(v);
                dfs(v, u);   // 递归调用
            }
        }
        if (children.size() >= 2) {
            // 统计每个子节点的平方自由部分的出现次数
            Map<Integer, Integer> cnt = new HashMap<>();
            for(int v: children){
                cnt.put(f[v], cnt.getOrDefault(f[v], 0) + 1);
            }
            for (int c : cnt.values()) {
                if (c > 1) ans += c - 1;
            }
        }
    }
}
class Read{
    StringTokenizer st = new StringTokenizer("");
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String next() throws IOException{
        while(!st.hasMoreTokens()){
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }
    int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
    double nextDouble() throws IOException{
        return Double.parseDouble(next());
    }
    long nextLong() throws IOException{
        return Long.parseLong(next());
    }
}